﻿#pragma once

//主模板 HashFunc<K> 提供默认行为，适用于可以直接转换为 size_t 的类型（如 int、long、char 等）。
template <class K>
struct HashFunc {
	size_t operator()(const K& key) { return (size_t)key; }
};

//特化版本 HashFunc<string> 针对 string 类型，提供更合理的哈希计算方式（BKDR Hash）。
template <>
struct HashFunc<string> {
	size_t operator()(const string& key) {
		size_t hash = 0;
		for (auto e : key) {
			hash *= 31;//为了解决"abc" "acb"结果相同(BKDR)
			hash += e;
		}
		return hash;//返回string中所有字符ASCII码值相加		
	}
};
//标准库中的unordered_map并不需要手动传第三个参数就可以处理string
//因为使用的是模版特化
//struct HashFuncString {
//	size_t operator()(const string& key) { 
//		size_t hash = 0;
//		for (auto e : key) {
//			hash *= 31;//为了解决"abc" "acb"结果相同(BKDR)
//			hash += e;
//		}			
//		return hash;//返回string中所有字符ASCII码值相加		
//	}
//};



//开散列 / 链地址法(开链法)
namespace hash_bucket {
	//template <class K, class V>
	template <class T>//类似红黑树，改为泛型。不管什么数据类型都用T接收
	struct HashNode {
		HashNode<T>* _next;
		T _data;

		HashNode(const T& data)
			:_next(nullptr)
			, _data(data) {
		}
	};

	//为解决迭代器要用哈希表，哈希表在下面找不到。使用前置声明(不要缺省参数)
	template <class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template <class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
	struct __HTIterator {
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
		Node* _node;
		//迭代器要用哈希表，哈希表在下面找不到
		const HashTable<K, T, KeyOfT, Hash>* _pht;
		//vector<Node*>* _pf;//这种方式也可以解决前后依赖

		size_t _hashi;//方法二：直接给出

		__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
			:_node(node), _pht(pht), _hashi(hashi) {
		}

		//这个用于构造const迭代器。const迭代器有const修饰this(即有const修饰的this指向哈希表)
		__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
			:_node(node), _pht(pht), _hashi(hashi) {
		}

		Self& operator++() {
			//begin()的实现确保返回第一个有效桶，所以可以直接判断
			if (_node->_next) {
				//当前桶还有节点，找下一个节点
				_node = _node->_next;
			}
			else {
				//当前桶遍历完，找下一个不为空的桶。
				//找下一个桶需要HashTable 或 vector<Node*>
				//方法一：现算hashi
				//Hash hf;
				//KeyOfT kot;
				//size_t hashi = hf(kot(_node->_data)) % _pht->_tables.size();
				++_hashi;
				while (_hashi < _pht->_tables.size()) { //_tables是HashTable的私有成员，访问不了
					if (_pht->_tables[_hashi]) { //如果有桶
						_node = _pht->_tables[_hashi];//_node从这开始遍历
						break;
					}
					++_hashi;
				}
				if (_hashi == _pht->_tables.size()) _node = nullptr;//遍历完哈希表
			}
			return *this;
		}

		bool operator!=(const Self& s) { return _node != s._node; }
		Ref operator*() { return _node->_data; }
		Ptr operator->() { return &_node->_data; }
	};

	//unordered_set -> HashTable<K, K>
	//unordered_set -> HashTable<K, pair<K, V>>
	template <class K, class T, class KeyOfT, class Hash>
	class HashTable {
		typedef HashNode<T> Node;
		//为了迭代器能访问HashTable的私有成员_tables，做类模板的友元声明
		template <class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
		friend struct __HTIterator;
	public:
		typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
		typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
		iterator begin() {
			for (size_t i = 0; i < _tables.size(); i++)
				if (_tables[i])
					return iterator(_tables[i], this, i);
			return end();
		}
		iterator end() { return iterator(nullptr, this, -1); }

		//this -> const HashTable<K, T, KeyOfT, Hash>*
		//这里的this是const修饰的，但迭代器的构造函数中使用的参数是非const
		//const不能传给非const
		const_iterator begin() const {
			for (size_t i = 0; i < _tables.size(); i++)
				if (_tables[i])
					return const_iterator(_tables[i], this, i);
			return end();
		}
		const_iterator end() const { return const_iterator(nullptr, this, -1); }

		//vector<Node*> 调用 resize(10) 后，所有指针会被默认初始化为 nullptr
		//（因为 Node* 是内置指针类型，默认初始化是未定义的，但 resize 会进行值初始化，即 nullptr）。
		HashTable() { _tables.resize(10, nullptr); }

		//因为哈希桶的vector每个位置的数据是一串链表
		//自动生成的析构只会释放vector，所以需要自己实现析构去释放链表
		~HashTable() {
			for (size_t i = 0; i < _tables.size(); i++) {
				Node* cur = _tables[i];
				while (cur) {
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		pair<iterator, bool> Insert(const T& data) {
			Hash hf;
			KeyOfT kot;
			iterator it = Find(kot(data));
			if (it != end()) return make_pair(it, false);//不允许重复key

			if (_n == _tables.size()) {
				vector<Node*> newTables;
				newTables.resize(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++) {
					Node* cur = _tables[i];
					while (cur) {
						Node* next = cur->_next;
						//hf是将数据转换为size_t；kot是取数据的key的值
						size_t hashi = hf(kot(cur->_data)) % newTables.size();
						cur->_next = newTables[hashi];
						newTables[hashi] = cur;
						cur = next;
					}
					_tables[i] = nullptr;//旧表中i的位置依然指向新表，如果不置空，析构会有问题
				}
				_tables.swap(newTables);
				//让 _tables 指向扩容后的新表。
				//让 newTables 接管旧表，通过析构自动释放内存。
			}
			size_t hashi = hf(kot(data)) % _tables.size();//key映射到哈希表的位置
			Node* newnode = new Node(data);
			//头插
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;
			++_n;
			return make_pair(iterator(newnode, this, hashi), true);
		}

		iterator Find(const K& key) {
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur) {
				if (kot(cur->_data) == key)
					return iterator(cur, this, hashi);
				cur = cur->_next;
			}
			return end();
		}

		bool Erase(const K& key) {
			Hash hf;
			KeyOfT kot;
			size_t hashi = hf(key) % _tables.size();
			Node* cur = _tables[hashi];
			Node* prev = nullptr;
			while (cur) { //遍历哈希桶
				if (kot(cur->_data) == key) { //如果找到了
					if (prev == nullptr) //且是第一个
						_tables[hashi] = cur->_next;
					else
						prev->_next = cur->_next;
					delete cur;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

		void Some() {
			size_t bucketSize = 0;//有多少个桶
			size_t maxBucketLen = 0;//单个桶最大长度
			size_t sum = 0;//元素总数
			double averageBucketLen = 0;//平均桶长度
			for (size_t i = 0; i < _tables.size(); i++) {
				Node* cur = _tables[i];
				if (cur) ++bucketSize;
				size_t bucketLen = 0;//单个桶长度
				while (cur) {
					++bucketLen;
					cur = cur->_next;
				}
				sum += bucketLen;
				if (bucketLen > maxBucketLen) maxBucketLen = bucketLen;
			}
			averageBucketLen = (double)sum / (double)bucketSize;
			cout << "all bucketSize:" << _tables.size() << endl;
			cout << "bucketSize:" << bucketSize << endl;
			cout << "maxBucketLen:" << maxBucketLen << endl;
			cout << "averageBucketLen:" << averageBucketLen << endl;
			cout << endl;
		}
	private:
		vector<Node*> _tables;
		size_t _n = 0;
	};

}